Міністерство освіти і науки України Національний університет «Львівська політехніка» кафедра САПР
Лабораторна робота №5 з курсу "Чисельні методи в інформатиці" на тему: ЧИСЕЛЬНІ МЕТОДИ РОЗВ'ЯЗУВАННЯ ТРАНСЦЕНДЕНТНИХ РІВНЯНЬ Виконав:cт. гр. КН-3 Львів-2008 1. МЕТА РОБОТИ Мета роботи - ознайомлення з чисельними методами розв'язку трансцендентних рівнянь та їх практичним застосуванням. 2. ТЕОРЕТИЧНА ЧАСТИНА 2.1. Методи розв'язування нелінійних рівнянь Розв'язування нелінійних рівнянь і систем є не тільки важливою самостійною задачею, але і частиною інших задач обчислювальної математики, наприклад, розв'язування нелінійних диференціальних рівнянь або знаходження власних значень матриць. З ними пов'язана побудова різноманітних моделей пристроїв і систем автоматики та інформаційно-вимірювальної техніки. 2.2. Методи бісекції розв'язку трансцендентних рівнянь. 2.2.1. Метод половинного ділення. В цьому методі спочатку обчислюються значення функції в точках, розміщених через рівні інтервали на осі x. Коли
і
мають протилежні знаки, то знаходять
та
Якщо знак
співпадає із знаком
, то в дальшому замість
використовується
. Якщо ж
має знак, протилежний знаку
, тобто співпадає зі знаком
, то на
заміняється це значення. Якщо
достатньо близьке до 0, то процес обчислення закінчується. Як умову припинення ітераційного процесу часто найбільш доцільно використовувати умову:
(1) де
- задана похибка знаходження кореня. Даний метод має малу швидкість збіжності. У порівнянні з початково знайденим інтервалом, в якому знаходиться корінь, його ширина після N ітерацій зменшується в 2N раз:
(2) Похибка знайденого рішення знаходиться в межах
(3) Ефективність даного методу:
(4) де n - кількість обчислень функції. 2.2.2. Метод золотого перерізу Алгоритм даного методу подібний до методу половинного ділен-ня, тільки поділ відрізка здійснюється виходячи із співвідношення золотого січення:
(5) Ефективність даного методу є більшою, ніж методу половинного ділення і оцінюється співвідношенням:
(6) 2.3. Метод хорд В основі цього методу лежить лінійна інтерполяція по двох значеннях функції, які мають протилежні знаки. При пошуку кореня метод забезпечує більшу збіжність, ніж попередні. Структура алгоритму представлена на рис.2. Визначаються значення функції в точках, розміщених на осі x через рівні інтервали. Це здійснюється до цього часу, поки
і
не будуть мати різних знаків. Пряма, проведена через ці дві точки, перетинає вісь x при значенні:
(7) Далі визначають
і порівнюють його з
і
. В подальшому користуються
замість того значення, з яким воно співпадає по знаку. Якщо
дуже відрізняється від 0, то вся процедура повторюється спочатку. При
можна вважати, що
. Це справедливо при вузькому інтервалі і коли похідна змінюється плавно (менше ніж у два рази). Похибка розв'язку оцінюється по формулі:
(8) де M1 і m1 - відповідно найбільше і найменше значення модуля похідної на відрізку
. 2.4. Метод Ньютона (дотичних) Метод Ньютона дуже широко використовується при побудові ітераційних алгоритмів. Його популярність пояснюється тим, що, на відміну від двох попередніх методів, для визначення інтервалу, в якому знаходиться корінь, не потрібно знаходити значення функції з протилежними знаками. Замість інтерполяції (наближення) по двох значеннях функції в методі Ньютона здійснюється екстраполяція (передбачення) за допомогою дотичної до кривої в даній точці. Структура алгоритму представлена на рис. 3. В основі методу лежить розклад функції в ряд Тейлора:
(9) члени, які містять h у другій і більших степенях відкидаються. Використовується співвідношення:
. Допускається, що перехід від xn до xn+1 наближує значення функції до нуля. Тоді:
(10) Це значення відповідає точці, в якій дотична до кривої перетинає вісь x. Після чого процедура повторюється, причому замість xn використовується xn+1. Обчислення припиняється при досягненні достатн...